package com.gorkr.labuladong.data_struct.struct;

import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.LinkedHashSet;

/**
 * @author gorkr
 * @date 2022/06/14 21:42
 **/
public class H460LFU {

    int capacity;
    HashMap<Integer, Integer> keyToVal;
    HashMap<Integer, Integer> keyToFreq;
    HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;
    int minFreq;


    public H460LFU() {
        this.capacity = 2;
        keyToVal = new HashMap<>();
        keyToFreq = new HashMap<>();
        freqToKeys = new HashMap<>();
        minFreq = 0;
    }

    public int get(int key) {
        if (!keyToVal.containsKey(key)) {
            return -1;
        }
        Integer val = keyToVal.get(key);
        // 增加key的访问频次
        increaseFreq(key);
        return val;
    }

    public void put(int key, int value) {

        if(capacity<=0){
            return;
        }

        // 如果key存在，更改其值
        if(keyToVal.containsKey(key)){
            keyToVal.put(key,value);
            increaseFreq(key);
            return;
        }
        // 如果key不存在
        // 如果缓存达到capacity 移除最不常使用的项
        if(keyToVal.size()>=capacity){
            removeMinFreq();
        }
        keyToVal.put(key,value);
        increaseFreq(key);
    }

    private void removeMinFreq(){
        Integer dropKey = freqToKeys.get(minFreq).iterator().next();
        freqToKeys.get(minFreq).remove(dropKey);
        if(freqToKeys.get(minFreq).isEmpty()){
            freqToKeys.remove(minFreq);
        }
        keyToFreq.remove(dropKey);
        keyToVal.remove(dropKey);
    }

    private void increaseFreq(Integer key){

        int beforeFreq = keyToFreq.getOrDefault(key,0);
        if(beforeFreq==0){
            keyToFreq.put(key,1);
            // 没有怎么增加？？？？
            freqToKeys.putIfAbsent(1,new LinkedHashSet<>());
            freqToKeys.get(1).add(key);
            minFreq = 1;
        }else {

            keyToFreq.put(key,beforeFreq+1);
            freqToKeys.get(beforeFreq).remove(key);
            if(freqToKeys.get(beforeFreq).isEmpty()){
                freqToKeys.remove(beforeFreq);
                if(beforeFreq==minFreq){
                    minFreq++;
                }
            }
            freqToKeys.putIfAbsent(beforeFreq+1,new LinkedHashSet<>());
            freqToKeys.get(beforeFreq+1).add(key);
        }
    }

    @Test
    public void test(){
        H460LFU h460LFU = new H460LFU();
        h460LFU.put(1,2);
        h460LFU.put(2,2);
        h460LFU.get(1);
        h460LFU.put(3,3);
        h460LFU.get(2);
        h460LFU.get(3);
        h460LFU.put(4,4);
        h460LFU.get(1);
        h460LFU.get(3);
        h460LFU.get(4);
    }


}
    